This invention relates to a buffer memory and, more particularly, to a buffer memory of the type provided in a data interface between devices, such as between a disc drive and one or more hosts, the memory being managed so as to support fragmented use thereof.
Interfaces commonly are provided between two or more data devices to permit data to be read from one device and supplied to the other. Such interfaces typically are provided between a data storage device and a data processing device, one example of the former being a disc storage device and one example of the latter being a host computer. A typical interface between a disc storage device, also known as a disc drive, and a host computer is the Small Computer System Interface (SCSI).
In general, an interface includes a temporary memory, such as a buffer memory, for storing data read from the disc drive in response to an access request by the host. The buffer memory is provided with addressable locations and the data is stored in "blocks" wherein each block of data is comprised of a predetermined number of bytes consistent with various conventional protocols. A controller cooperates with the buffer memory and usually operates to assign specific memory addresses to the respective data blocks read from or written to the disc drive and transferred to or from the host. The controller keeps track of those buffer addresses which are vacant as well as those which are occupied. The controller also keeps track of data blocks which have been called for from the disc drive by the host and have either been transferred to the host or are awaiting transfer.
During a typical "data read" operation, wherein data blocks are read from the disc drive, stored temporarily in the buffer memory and then transferred to the host, the host calls for a series of data blocks formed of a number of such blocks. In addition to retrieving the particular data blocks called for by the host, the controller operates to "prefetch" certain data blocks which, although not specifically called for, nevertheless are proximate those data blocks which have been requested and, thus, are reasonably expected to be called for in an ensuing read operation. Conventionally, the data blocks called for by the host as well as those which are prefetched by the controller are stored in successive buffer addresses. It will be appreciated that, over a period of time, that is, after several read operations, a significant number of data blocks may be stored in the buffer memory but not transferred to the host. For example, because of interruptions and other tasks carried out by the host, some data blocks which have been specifically called for might not yet have been read. As another example, many of the data blocks which were prefetched by the controller may not be requested and, thus, not retrieved, by the host. Consequently, the buffer memory will be provided with several filled addresses (i.e. addresses containing data blocks that have not yet been retrieved by the host) interspersed with available addresses (i.e. addresses which contained data blocks that have been retrieved). But, when a new series of data blocks is read or prefetched from the disc drive, the typical buffer memory and memory controller require those data blocks to be stored in sequential addresses. That is, such data blocks must be stored in consecutive addressable locations and cannot be stored in random addresses that nevertheless are available.
If the number of data blocks which are to be read from the disc drive exceeds the number of consecutive buffer addresses that are available to store those data blocks, the controller operates to determine which of the data blocks still stored in the buffer may be discarded or replaced by the new data blocks now called for by the host. This determination is made in accordance with a predetermined replacement algorithm known to those of ordinary skill in the art. Thus, data blocks which are unlikely to be transferred to the host are discarded. However, because of limitations in the storage capacity of the buffer, many data blocks which are discarded simply to enable the buffer to accommodate new data blocks read from the disc drive should have been retained. Consequently, useful data that had not yet been retrieved by the host is replaced by new data; and the replaced data thus is lost. Should the host now wish to be supplied with the data blocks that were discarded, a new data read operation must be executed, and the foregoing problem of replacing data blocks that have not yet been retrieved with new data blocks because of the requirement of storing data blocks in consecutive addresses is repeated.
It has been recognized that the effective use of a buffer memory will be improved if a series of data blocks called for by the host or prefetched by the buffer controller need not be stored in sequential addresses of the buffer memory. If a series of data blocks may be interspersed in the buffer with previously stored but not yet retrieved data blocks, the aforementioned problem of replacing useful data with new data would be substantially avoided. However, heretofore, an attempt to operate a buffer controller to permit such fragmentation of the buffer memory has been thought to be complicated and expensive. Special programming of the microprocessor normally used in the buffer controller likewise had been thought to be complicated and even beyond the operating capacity of the typical microprocessor. Hence, buffer fragmentation has not heretofore been permitted or supported in prior art buffer memories.